home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 333_02 / regex2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-04-21  |  13.9 KB  |  482 lines
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include "awk.h"
  6.  
  7.  
  8. /* Like re_match but tries first a match starting at index `startpos',      */
  9. /* then at startpos + 1, and so on.  `range' is the number of places to try */
  10. /* before giving up.  If `range' is negative, the starting positions tried  */
  11. /* are startpos, startpos - 1, etc.  It is up to the caller to make sure    */
  12. /* that range is not so large as to take the starting position outside of   */
  13. /* the input strings.  The value returned is the position at which the        */
  14. /* match was found, or -1 if no match was found.                */
  15.  
  16. int PASCAL re_search(REPAT_BUFFER *pbufp, char *string, int size,
  17.              int startpos, int range, REREGS *regs)
  18. {
  19.     register char      *fastmap   = pbufp->fastmap;
  20.  
  21.     /* Update the fastmap now if not correct already */
  22.     if (fastmap && !pbufp->fastmap_accurate)
  23.     re_compile_fastmap(pbufp);
  24.  
  25.     while (TRUE)
  26.     {
  27.     /* If a fastmap is supplied, skip quickly over characters that        */
  28.     /* cannot possibly be the start of a match. Note, however, that if  */
  29.     /* the pattern can possibly match the null string, we must test it  */
  30.     /* at each starting point so that we take the first null string we  */
  31.     /* get.                                 */
  32.     if (fastmap && startpos < size && pbufp->can_be_null != 1)
  33.     {
  34.         if (range > 0)
  35.         {
  36.         register int      lim = 0;
  37.         register char     *p;
  38.         auto     int      irange = range;
  39.  
  40.         if (startpos < size && startpos + range >= size)
  41.             lim = range - (size - startpos);
  42.  
  43.         p = &string[startpos];
  44.         while (range > lim && !fastmap[*p++])
  45.             range--;
  46.         startpos += irange - range;
  47.         }
  48.         else
  49.         {
  50.         register char   c;
  51.  
  52.         c = string[startpos];
  53.         if (!fastmap[c])
  54.             goto advance;
  55.         }
  56.     }
  57.  
  58.     if (range >= 0 && startpos == size
  59.         && fastmap && pbufp->can_be_null == 0)
  60.         return(-1);
  61.  
  62.     if (0 <= re_match(pbufp, string, size, startpos, regs))
  63.         return(startpos);
  64. advance:
  65.     if (!range)
  66.         break;
  67.     if (range > 0)
  68.     {
  69.         --range;
  70.         ++startpos;
  71.     }
  72.     else
  73.     {
  74.         ++range;
  75.         --startpos;
  76.     }
  77.     }
  78.     return(-1);
  79. }
  80.  
  81.  
  82. /* Match the pattern described by `pbufp' against data which is the virtual  */
  83. /* concatenation of `string1' and `string2'.  `size1' and `size2' are the    */
  84. /* sizes of the two data strings.  Start the match at position `pos'.    Do  */
  85. /* not consider matching past the position `mstop'.  If pbufp->fastmap is    */
  86. /* nonzero, then it had better be up to date.                     */
  87. /*                                         */
  88. /* The reason that the data to match is specified as two components which    */
  89. /* are to be regarded as concatenated is so that this function can be used   */
  90. /* directly on the contents of an Emacs buffer.  -1 is returned if there is  */
  91. /* no match.  Otherwise the value is the length of the substring which was   */
  92. /* matched.                                     */
  93.  
  94. int PASCAL re_match(REPAT_BUFFER *pbufp, char *string, int size,
  95.             int pos, REREGS *regs)
  96. {
  97.     register int      op;
  98.     register char     *p    = pbufp->buffer;
  99.     register char     *pend = p + pbufp->used;
  100.     auto     char     *end;               /* end of string */
  101.     auto     char     *end_match;
  102.     register char     *d, *dend;
  103.     register int      mcnt;
  104.  
  105.     /* Failure point stack.  Each place that can handle a failure further
  106.      * down the line pushes a failure point on this stack.  It consists of
  107.      * two char *'s. The first one pushed is where to resume scanning the
  108.      * pattern; the second pushed is where to resume scanning the strings. If
  109.      * the latter is zero, the failure point is a "dummy". If a failure
  110.      * happens and the innermost failure point is dormant, it discards that
  111.      * failure point and tries the next one. */
  112.  
  113.     static   int      stacksiz = 0;
  114.     static   char    **stackb   = NULL;
  115.     auto     char    **stackp, **stacke;
  116.  
  117.     /* Information on the "contents" of registers. These are pointers into
  118.      * the input strings; they record just what was matched (on this attempt)
  119.      * by some part of the pattern. The start_memory command stores the start
  120.      * of a register's contents and the stop_memory command stores the end. 
  121.      *
  122.      * At that point, regstart[regnum] points to the first character in the
  123.      * register, regend[regnum] points to the first character beyond the end
  124.      * of the register, and regstart_segend[regnum] is either the same as
  125.      * regend[regnum] or else points to the end of the input string into
  126.      * which regstart[regnum] points. The latter case happens when
  127.      * regstart[regnum] is in string1 and regend[regnum] is in string2.  */
  128.  
  129.     auto     char     *regstart[RE_NREGS];
  130.     auto     char     *regstart_segend[RE_NREGS];
  131.     auto     char     *regend[RE_NREGS];
  132.     static   char      outmem_msg[] = "Out of memory in re_match()";
  133.  
  134.  
  135.     if (0 == stacksiz)
  136.     {
  137.     stacksiz = 2 * NFAILURES;
  138.     if (NULL == (stackb = (char **) malloc(stacksiz * sizeof(char *))))
  139.         panic(outmem_msg);
  140.     }
  141.     stackp = stackb;
  142.     stacke = stackb + stacksiz;
  143.  
  144.     end = string + size;
  145.  
  146.     /* Compute where to stop matching, within the two strings */
  147.     end_match = string + size;
  148.  
  149.     /* Initialize \( and \) text positions to -1 to mark ones that no \( or */
  150.     /* \) has been seen for.                            */
  151.     for (mcnt = 0; mcnt < sizeof(regstart) / sizeof(*regstart); mcnt++)
  152.     regstart[mcnt] = (char *) -1;
  153.  
  154.     /* `p' scans through the pattern as `d' scans through the data. `dend' is
  155.      * the end of the input string that `d' points within. `d' is advanced
  156.      * into the following input string whenever necessary, but this happens
  157.      * before fetching; therefore, at the beginning of the loop, `d' can be
  158.      * pointing at the end of a string, but it cannot equal string2.  */
  159.  
  160.     d     = string + pos;
  161.     dend = end_match;
  162.  
  163.     /* This loop loops over pattern commands. It exits by returning from the
  164.      * function if match is complete, or it drops through if match fails at
  165.      * this starting point in the input data. */
  166.  
  167.     while (TRUE)
  168.     {
  169.     if (p == pend)
  170.         /* End of pattern means we have succeeded! */
  171.     {
  172.         /* If caller wants register contents data back, convert it to
  173.          * indices */
  174.         if (regs)
  175.         {
  176.         regend[0]   = d;
  177.         regstart[0] = string;
  178.         for (mcnt = 0; mcnt < RE_NREGS; mcnt++)
  179.         {
  180.             if ((mcnt != 0) && regstart[mcnt] == (char *) -1)
  181.             {
  182.             regs->start[mcnt] = -1;
  183.             regs->end[mcnt] = -1;
  184.             continue;
  185.             }
  186.             regs->start[mcnt] = regstart[mcnt] - string;
  187.             regs->end[mcnt] = regend[mcnt] - string;
  188.         }
  189.         regs->start[0] = pos;
  190.         }
  191.         return(d - string - pos);
  192.     }
  193.  
  194.     /* Otherwise match next pattern command */
  195.     op = *p++;
  196.     switch (op)
  197.     {
  198.         /* \( is represented by a start_memory, \) by a stop_memory.
  199.          * Both of those commands contain a "register number"
  200.          * argument. The text matched within the \( and \) is
  201.          * recorded under that number. Then, \<digit> turns into a
  202.          * `duplicate' command which is followed by the numeric value
  203.          * of <digit> as the register number. */
  204.  
  205.         case RECODE_START_MEMORY:
  206.         regstart[*p] = d;
  207.         regstart_segend[*p++] = dend;
  208.         break;
  209.  
  210.         case RECODE_STOP_MEMORY:
  211.         regend[*p] = d;
  212.         if (regstart_segend[*p] == dend)
  213.             regstart_segend[*p] = d;
  214.         p++;
  215.         break;
  216.  
  217.         case RECODE_DUPLICATE:
  218.         {
  219.             int         regno = *p++;    /* Get which register to
  220.                               * match against */
  221.             register char  *d2, *dend2;
  222.  
  223.             d2 = regstart[regno];
  224.             dend2 = regstart_segend[regno];
  225.             while (TRUE)
  226.             {
  227.             /* At end of register contents => success */
  228.             if (d2 == dend2)
  229.                 break;
  230.  
  231.             /* mcnt gets # consecutive chars to compare */
  232.             mcnt = dend - d;
  233.             if (mcnt > dend2 - d2)
  234.                 mcnt = dend2 - d2;
  235.             /* Compare that many; failure if mismatch, else skip
  236.              * them. */
  237.             if (bcmp(d, d2, mcnt))
  238.                 goto fail;
  239.             d += mcnt, d2 += mcnt;
  240.             }
  241.         }
  242.         break;
  243.  
  244.         case RECODE_ANYCHAR:
  245.         /* Match anything but a newline.  */
  246.         if (*d++ == '\n')
  247.             goto fail;
  248.         break;
  249.  
  250.         case RECODE_CHARSET:
  251.         case RECODE_CHARSET_NOT:
  252.         {
  253.             /* Nonzero for charset_not */
  254.             auto     int    not = 0;
  255.             register int    c;
  256.  
  257.             if (*(p - 1) == RECODE_CHARSET_NOT)
  258.             not = 1;
  259.  
  260.             c = *(unsigned char *) d;
  261.  
  262.             if (c < *p * BYTEWIDTH
  263.             && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
  264.             not = !not;
  265.  
  266.             p += 1 + *p;
  267.  
  268.             if (!not)
  269.             goto fail;
  270.             d++;
  271.             break;
  272.         }
  273.  
  274.         case RECODE_BEGLINE:
  275.         if (d == string || d[-1] == '\n')
  276.             break;
  277.         goto fail;
  278.  
  279.         case RECODE_ENDLINE:
  280.         if (d == end || *d == '\n')
  281.             break;
  282.         goto fail;
  283.  
  284.         /* "or" constructs ("|") are handled by starting each
  285.          * alternative with an on_failure_jump that points to the
  286.          * start of the next alternative. Each alternative except the
  287.          * last ends with a jump to the joining point. (Actually,
  288.          * each jump except for the last one really jumps to the
  289.          * following jump, because tensioning the jumps is a hassle.) */
  290.  
  291.         /* The start of a stupid repeat has an on_failure_jump that
  292.          * points past the end of the repeat text. This makes a
  293.          * failure point so that, on failure to match a repetition,
  294.          * matching restarts past as many repetitions have been found
  295.          * with no way to fail and look for another one.  */
  296.  
  297.         /* A smart repeat is similar but loops back to the
  298.          * on_failure_jump so that each repetition makes another
  299.          * failure point. */
  300.  
  301.         case RECODE_ON_FAILURE_JUMP:
  302.         if (stackp == stacke)
  303.         {
  304.             auto     char     **stackx;
  305.  
  306.             stacksiz = stacksiz + (2 * NFAILURES);
  307.             stackx   = (char **) realloc(stackb,
  308.                          stacksiz * sizeof(char *));
  309.             if (NULL == stackx)
  310.             panic(outmem_msg);
  311.             stackp = stackx + (stackp - stackb);
  312.             stacke = stackx + stacksiz;
  313.             stackb = stackx;
  314.         }
  315.         mcnt = *p++ & 0377;
  316.         mcnt += SIGN_EXTEND_CHAR(*p) << 8;
  317.         p++;
  318.         *stackp++ = p + mcnt;
  319.         *stackp++ = d;
  320.         break;
  321.  
  322.         /* The end of a smart repeat has an maybe_finalize_jump back.
  323.          * Change it either to a finalize_jump or an ordinary jump. */
  324.  
  325.         case RECODE_MAYBE_FINALIZE_JUMP:
  326.         mcnt = *p++ & 0377;
  327.         mcnt += SIGN_EXTEND_CHAR(*p) << 8;
  328.         p++;
  329.         /* Compare what follows with the begining of the repeat. If
  330.          * we can establish that there is nothing that they would
  331.          * both match, we can change to finalize_jump */
  332.         if (p == pend)
  333.             p[-3] = RECODE_FINALIZE_JUMP;
  334.         else
  335.         if (*p == RECODE_EXACTN || *p == RECODE_ENDLINE)
  336.         {
  337.             register int    c = *p == RECODE_ENDLINE ? '\n' : p[2];
  338.             register char  *p1 = p + mcnt;
  339.  
  340.             /* p1[0] ... p1[2] are an on_failure_jump. Examine what
  341.              * follows that */
  342.             if (p1[3] == RECODE_EXACTN && p1[5] != c)
  343.             p[-3] = RECODE_FINALIZE_JUMP;
  344.             else
  345.             if (p1[3] == RECODE_CHARSET || p1[3] == RECODE_CHARSET_NOT)
  346.             {
  347.             int        not = p1[3] == RECODE_CHARSET_NOT;
  348.  
  349.             if (c < p1[4] * BYTEWIDTH
  350.               && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
  351.                 not = !not;
  352.             /* not is 1 if c would match */
  353.             /* That means it is not safe to finalize */
  354.             if (!not)
  355.                 p[-3] = RECODE_FINALIZE_JUMP;
  356.             }
  357.         }
  358.         p -= 2;
  359.         if (p[-1] != RECODE_FINALIZE_JUMP)
  360.         {
  361.             p[-1] = RECODE_JUMP;
  362.             goto nofinalize;
  363.         }
  364.  
  365.         /* The end of a stupid repeat has a finalize-jump back to the
  366.          * start, where another failure point will be made which will
  367.          * point after all the repetitions found so far. */
  368.  
  369.         case RECODE_FINALIZE_JUMP:
  370.         stackp -= 2;
  371.  
  372.         case RECODE_JUMP:
  373. nofinalize:
  374.         mcnt = *p++ & 0377;
  375.         mcnt += SIGN_EXTEND_CHAR(*p) << 8;
  376.         p += mcnt + 1;    /* The 1 compensates for missing ++ above */
  377.         break;
  378.  
  379.         case RECODE_DUMMY_FAILURE_JUMP:
  380.         if (stackp == stacke)
  381.         {
  382.             auto     char     **stackx;
  383.  
  384.             stacksiz = stacksiz + (2 * NFAILURES);
  385.             stackx   = (char **) realloc(stackb,
  386.                          stacksiz * sizeof(char *));
  387.             if (NULL == stackx)
  388.             panic(outmem_msg);
  389.             stackp = stackx + (stackp - stackb);
  390.             stacke = stackx + stacksiz;
  391.             stackb = stackx;
  392.         }
  393.         *stackp++ = NULL;
  394.         *stackp++ = NULL;
  395.         goto nofinalize;
  396.  
  397.         case RECODE_WORDBOUND:
  398.         if (d == string || d == end)
  399.             break;
  400.         if ((SYNTAX(((unsigned char *) d)[-1]) == Sword)
  401.             != (SYNTAX(*(unsigned char *) d) == Sword))
  402.             break;
  403.         goto fail;
  404.  
  405.         case RECODE_NOTWORDBOUND:
  406.         if (d == string || d == end)
  407.             goto fail;
  408.         if ((SYNTAX(((unsigned char *) d)[-1]) == Sword)
  409.             != (SYNTAX(*(unsigned char *) d) == Sword))
  410.             goto fail;
  411.         break;
  412.  
  413.         case RECODE_WORDBEG:
  414.         if (d == end
  415.               || SYNTAX(*(unsigned char *) (d)) != Sword)
  416.             goto fail;
  417.         if (d == string
  418.               || SYNTAX(((unsigned char *) d)[-1]) != Sword)
  419.             break;
  420.         goto fail;
  421.  
  422.         case RECODE_WORDEND:
  423.         if (d == string
  424.               || SYNTAX(((unsigned char *) d)[-1]) != Sword)
  425.             goto fail;
  426.         if (d == end || SYNTAX(*(unsigned char *) d) != Sword)
  427.             break;
  428.         goto fail;
  429.  
  430.         case RECODE_WORDCHAR:
  431.         if (SYNTAX(*(unsigned char *) d++) == 0)
  432.             goto fail;
  433.         break;
  434.  
  435.         case RECODE_NOTWORDCHAR:
  436.         if (SYNTAX(*(unsigned char *) d++) != 0)
  437.             goto fail;
  438.         break;
  439.  
  440.         case RECODE_BEGBUF:
  441.         if (d == string)
  442.             break;
  443.         goto fail;
  444.  
  445.         case RECODE_ENDBUF:
  446.         if (d == end)
  447.             break;
  448.         goto fail;
  449.  
  450.         case RECODE_EXACTN:
  451.         /* Match the next few pattern characters exactly. mcnt is how
  452.          * many characters to match. */
  453.         mcnt = *p++;
  454.         do
  455.         {
  456.             if (*d++ != *p++)
  457.             goto fail;
  458.         } while (--mcnt);
  459.         break;
  460.     }
  461.     continue;        /* Successfully matched one pattern command;
  462.                  * keep matching */
  463.  
  464.     /* Jump here if any matching operation fails. */
  465. fail:
  466.     if (stackp == stackb)
  467.         break;        /* Matching at this start point fails     */
  468.  
  469.     /* A restart point is known.  Restart there and pop it.      */
  470.     if (!(*(stackp - 2)))    /* If innermost failure point is dormant */
  471.     {            /* flush it and keep looking         */
  472.         stackp -= 2;
  473.         goto fail;
  474.     }
  475.     d = *--stackp;
  476.     p = *--stackp;
  477.     if (d >= string && d <= end)
  478.         dend = end_match;
  479.     }
  480.     return(-1);         /* Failure to match */
  481. }
  482.